/*
 * @FilePath: /data-and-structure-lv/15/matrix-chain-order.c
 * @Brief: 
 * @Version: 1.0
 * @Date: 2022-01-02 18:02:35
 * @Author: zsk
 * @Copyright: open source
 * @LastEditors: zsk
 * @LastEditTime: 2022-01-03 13:32:33
 */
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

typedef struct MatrixChainOrder_Tag
{
    int **m;
    int **s;
} MatrixChainOrder;

int **create_two_array(int rows, int cols)
{
    int **m = malloc(sizeof(int *) * (rows + 1));
    for (int i = 0; i <= rows; i++)
    {
        m[i] = malloc(sizeof(int) * (cols + 1));
    }
    return m;
}

void release_two_array(int **m, int rows, int cols)
{
    for (int i = 0; i <= rows; i++)
    {
        free(m[i]);
    }
    free(m);
}

MatrixChainOrder *matrix_chain_order(int *p, int n)
{
    int **m = create_two_array(n, n);
    m[0][0] = INT_MIN;
    int **s = create_two_array(n - 1, n);
    s[0][0] = INT_MIN;

    for (int i = 1; i <= n; i++)
    {
        m[i][i] = 0;
    }
    for (int l = 2; l <= n; l++)
    {
        for (int i = 1; i <= n - l + 1; i++)
        {
            int j = i + l - 1;
            m[i][j] = INT_MAX;
            int q;
            for (int k = i; k <= j - 1; k++)
            {
                q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
                if (q < m[i][j])
                {
                    m[i][j] = q;
                    s[i][j] = k;
                }
            }
        }
    }
    MatrixChainOrder *mco = malloc(sizeof(MatrixChainOrder));
    mco->m = m;
    mco->s = s;
    return mco;
}

void print_optimal_parens(int **s, int i, int j)
{
    if (i == j)
    {
        printf("A");
    }
    else
    {
        printf("(");
        print_optimal_parens(s, i, s[i][j]);
        print_optimal_parens(s, s[i][j] + 1, j);
        printf(")");
    }
}

void main()
{
    // int p[] = {10, 100, 5, 50};
    // int n = 3;
    // MatrixChainOrder *mco = matrix_chain_order(p, n);
    // print_optimal_parens(mco->s, 1, 3);
    // printf("\n");
    // release_two_array(mco->s, n - 1, n);
    // release_two_array(mco->m, n, n);
    // free(mco);

    // int p[] = {30, 35, 15, 5, 10, 20, 25};
    // int n = 6;
    // MatrixChainOrder *mco = matrix_chain_order(p, n);
    // print_optimal_parens(mco->s, 1, 6);
    // printf("\n");
    // release_two_array(mco->s, n - 1, n);
    // release_two_array(mco->m, n, n);
    // free(mco);

    int p[]={5,10,3,12,5,50,6};
    int n = 6;
    MatrixChainOrder *mco = matrix_chain_order(p, n);
    print_optimal_parens(mco->s, 1, 6);
    printf("\n");
    release_two_array(mco->s, n - 1, n);
    release_two_array(mco->m, n, n);
    free(mco);
}
